/* Copyright 2010 Michael Bruno
 *
 * This file is part of AYACE
 *
 * AYACE is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * at your option) any later version.
 *
 * AYACE is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with AYACE.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>
#include "common.h"
#include "bitboard/bitboard.h"
#include "bitboard/bitboard_init.h"
#include "bitboard/bitboard_movelist.h"
#include "chess.h"
#include "hash.h"
#include "move_search.h"

#define QUIESCENCE_SEARCH 1
#define ORDER_MOVES 0
#define NEGASCOUT 1
#define SEARCH_EXTENSIONS 0
#define TRANSPOSITION_TABLE 0

// Position score tables taken from:
// http://www.chessbin.com/post/Chess-Board-Evaluation.aspx

static const int pawn_position_score[64] = {
	 0,  0,  0,  0,  0,  0,  0,  0,
	50, 50, 50, 50, 50, 50, 50, 50,
	10, 10, 20, 30, 30, 20, 10, 10,
	 5,  5, 10, 27, 27, 10,  5,  5,
	 0,  0,  0, 25, 25,  0,  0,  0,
	 5, -5,-10,  0,  0,-10, -5,  5,
	 5, 10, 10,-25,-25, 10, 10,  5,
	 0,  0,  0,  0,  0,  0,  0,  0
};

static const int knight_position_score[64] = {
	-50,-40,-30,-30,-30,-30,-40,-50,
	-40,-20,  0,  0,  0,  0,-20,-40,
	-30,  0, 10, 15, 15, 10,  0,-30,
	-30,  5, 15, 20, 20, 15,  5,-30,
	-30,  0, 15, 20, 20, 15,  0,-30,
	-30,  5, 10, 15, 15, 10,  5,-30,
	-40,-20,  0,  5,  5,  0,-20,-40,
	-50,-40,-20,-30,-30,-20,-40,-50
};

static const int bishop_position_score[64] = {
	-20,-10,-10,-10,-10,-10,-10,-20,
	-10,  0,  0,  0,  0,  0,  0,-10,
	-10,  0,  5, 10, 10,  5,  0,-10,
	-10,  5,  5, 10, 10,  5,  5,-10,
	-10,  0, 10, 10, 10, 10,  0,-10,
	-10, 10, 10, 10, 10, 10, 10,-10,
	-10,  5,  0,  0,  0,  0,  5,-10,
	-20,-10,-40,-10,-10,-40,-10,-20
};

static const int king_position_score[64] = {
	-30, -40, -40, -50, -50, -40, -40, -30,
	-30, -40, -40, -50, -50, -40, -40, -30,
	-30, -40, -40, -50, -50, -40, -40, -30,
	-30, -40, -40, -50, -50, -40, -40, -30,
	-20, -30, -30, -40, -40, -30, -30, -20,
	-10, -20, -20, -20, -20, -20, -20, -10,
	 20,  20,   0,   0,   0,   0,  20,  20,
	 20,  30,  10,   0,   0,  10,  30,  20
};

move_t killer_move[32];

inline int piece_score(int piece)
{
	switch (piece) {
	case PAWN:
		return 1;
	case KNIGHT:
		return 3;
	case BISHOP:
		return 3;
	case ROOK:
		return 5;
	case QUEEN:
		return 9;
	case KING:
		return 200;
	default:
		return 0;
	}
}

inline int piece_value_sum(board_t *b, bitboard mask, int color)
{
	int value;

	value = __builtin_popcountll(b->color[color].pawns & mask) * piece_score(PAWN);
	value += __builtin_popcountll(b->color[color].knights & mask) * piece_score(KNIGHT);
	value += __builtin_popcountll(b->color[color].bishops & mask) * piece_score(BISHOP);
	value += __builtin_popcountll(b->color[color].rooks & mask) * piece_score(ROOK);
	value += __builtin_popcountll(b->color[color].queens & mask) * piece_score(QUEEN);
	value += __builtin_popcountll(b->color[color].king & mask) * piece_score(KING);

	return value;
}

int board_score(board_t *b)
{
	int sq, position_index;
	int piece, color;
	int sm, score = 0;

	bitboard my_attacks, all_pieces;

	all_pieces = b->all_pieces;
	
	while (all_pieces) {
		sq = last_one_64(all_pieces);
		all_pieces = BITCLEAR(all_pieces, sq);
		color = get_piece_color(b, sq);
		piece = get_piece_type(b, sq, color);
		sm = (color == current_color ? 1 : -1);

		// count empty defended squares
		my_attacks = get_attacks_from(b, sq, piece, color);
		score += __builtin_popcountll(my_attacks & ~b->all_pieces) * 1 * sm;

		// award forks
	//	score += MAX(2, __builtin_popcountll(my_attacks & b->color[!color].all)) * 5 * sm;

		// award defended pieces
	//	my_attacks = get_attacks_to(b, sq, color);
	//	score += MAX(2, __builtin_popcountll(my_attacks)) * 5 * sm;

		// penalize blocked pawns
		if (piece == PAWN) {
			score -= __builtin_popcountll(pawn_moves[color][sq] & b->all_pieces) * 10 * sm;
		}
		
		// add value of each piece
		score += piece_score(piece) * 100 * sm;

		// add score of position of each piece
		position_index = color == BLACK ? sq : 63-sq;
		switch (piece) {
		case PAWN:
			score += pawn_position_score[position_index] * sm;
			break;
		case KNIGHT:
			score += knight_position_score[position_index] * sm;
			break;
		case BISHOP:
			score += bishop_position_score[position_index] * sm;
			break;
		case KING:
			score += king_position_score[position_index] * sm;
			break;
		}
	}
	
	return score;// + (rand() % 11 - 5);
}

#if ORDER_MOVES
list_node *order_move_list(board_t *b, list_node *move_list)
{
	list_node *capture_head = NULL, *capture = NULL;
	list_node *pawn_push_head = NULL, *pawn_push = NULL;
	list_node *rest_head = NULL, *rest = NULL;
	list_node *next, *curnode;
	move_t *m;
	int is_capture = 0, is_pawn_push = 0, is_rest = 0;

	yurnode = move_list;
	while (curnode != NULL) {
		next = curnode->next;
		m = &(curnode->move);
		get_init_move_info(b, m);
		if (m->mi.move_type == CAPTURE) {
			if (capture != NULL) {
				capture->next = curnode;
				curnode->prev = capture;;
				capture = curnode;
				capture->next = NULL;
			} else {
				is_capture = 1;
				capture = capture_head = curnode;
				capture->prev = NULL;
				capture->next = NULL;
			}
		} else if (m->mi.new_piece == 'p') {
			if (pawn_push != NULL) {
				pawn_push->next = curnode;
				curnode->prev = pawn_push;;
				pawn_push = curnode;
				pawn_push->next = NULL;
			} else {
				is_pawn_push = 1;
				pawn_push = pawn_push_head = curnode;
				pawn_push->prev = NULL;
				pawn_push->next = NULL;
			}
		} else {
			if (rest != NULL) {
				rest->next = curnode;
				curnode->prev = rest;;
				rest = curnode;
				rest->next = NULL;
			} else {
				is_rest = 1;
				rest = rest_head = curnode;
				rest->prev = NULL;
				rest->next = NULL;
			}
		}
		curnode = next;
	}

	if (is_capture) {
		move_list = capture_head;
		if (is_pawn_push) {
			capture->next = pawn_push_head;
			pawn_push_head->prev = capture;
			if (is_rest) {
				pawn_push->next = rest_head;
				rest_head->prev = pawn_push;
			}
		} else if (is_rest) {
			capture->next = rest_head;
			rest_head->prev = capture;
		}
	} else if (is_pawn_push) {
		move_list = pawn_push_head;
		if (is_rest) {
			pawn_push->next = rest_head;
			rest_head->prev = pawn_push;
		}
	} else if (is_rest) {
		move_list = rest_head;
	} else {
		move_list = NULL;
	}

	return move_list;
}
#endif


// alpha beta fail-soft negascout search with transposition table
int board_score_deep(board_t *b, move_t last_move, int color, int search_depth, int se, int alpha, int beta, int ply, int *evals)
{
	int i, sm, score, best_score, beta2, o_alpha = alpha, o_beta = beta;
	int fail;
	int tried_killer_move, tried_hash_move = 1;
	uint64_t key;
	ttable_entry *te;
	int moved = 0;
	int next_search_depth = search_depth - 1;
	int move_count;
	move_t m, move_list_ar[256], *move_list, kmove, hash_move, best_move;
	board_t b2;
	
	move_list = move_list_ar;
	sm = (color != current_color ? -1 : 1);

#if TRANSPOSITION_TABLE
	key = gen_zobrist_key(b, color);
	te = ttable_lookup(ttable, key);
	if (te->key == key) {
		if (te->ply == ply) {
			if (te->depth == search_depth) {
				if (te->fail == 0 && alpha >= te->alpha && beta <= te->beta) {
			//	if (te->fail == 0 && alpha == te->alpha && beta == te->beta) {
				//	return MAX(alpha,MIN(beta, (int)te->score));
					return te->score;
				} else if (te->fail < 0) {
			//		beta = MIN((int)te->score, beta);
			//		alpha = MIN(beta, alpha);
				} else if (te->fail > 0) {
			//		alpha = MAX((int)te->score, alpha);
			//		beta = MAX(beta, alpha);
				}
			} else {
				if (te->fail >= 0) {
					hash_move = te->best_move;
					tried_hash_move = 0;
				}
			}
		}
	}
#endif

#if SEARCH_EXTENSIONS
	// search extensions:
	if (search_depth == 0 && se == 0) {
		if (mi->move_type == CAPTURE) {
		//	se = 1;
		//	next_search_depth = 1;
		} else if ((b->checked[WHITE] || b->checked[BLACK])) {
			// look one move deeper if at end of depth and either side is in check
			// this way we can see if we are in checkmate and at max depth
			se = 1;
			next_search_depth = 1;
		}
	}
#endif

	if (next_search_depth >= 0) {
		move_count = get_move_list(b, move_list, color);
#if ORDER_MOVES
		move_list = order_move_list(b, move_list);
#endif
		
		if (in_list(move_list, move_count, killer_move[ply-1], &kmove)) {
			tried_killer_move = 0;
		} else {
			tried_killer_move = 1;
		}

		if (!tried_hash_move) {
			if (!in_list(move_list, move_count, hash_move, &hash_move)) {
				tried_hash_move = 1;
			}
		}


		fail = -1;
		best_score = -INT_MAX;
		best_move.to = 0; best_move.from = 0;
#if NEGASCOUT
		beta2 = beta;
#endif
		for (i=0; i<move_count; i++) {
			if (tried_killer_move && tried_hash_move) {
				m = *move_list++;
				if ((tried_killer_move == 2 && m.to == kmove.to && m.from == kmove.from) ||
				    (tried_hash_move == 2 && m.to == hash_move.to && m.from == hash_move.from)) {
					// don't try killer or hash move twice
					continue;
				}
			} else if (!tried_hash_move) {
				i--;
				m = hash_move;
				tried_hash_move = 2;
			} else {
				i--;
				m = kmove;
				tried_killer_move = 2;
			}


			b2 = *b;
			if (move_piece(b, m, color)) {
				// move leaves king in check
				continue;
			}
			moved = 1;
#if NEGASCOUT			
			score = -board_score_deep(b, m, !color, next_search_depth, se, -beta2, -alpha, ply+1, evals);
			
			//negascout
			if (alpha < score && score < beta && i != 0) {
#endif				
				score = -board_score_deep(b, m, !color, next_search_depth, se, -beta, -alpha, ply+1, evals);
#if NEGASCOUT
			}
#endif
			// undo move
			*b = b2;

			if (score > alpha) {
				fail = 0;
				alpha = score;

				if (alpha >= beta) {
					fail = 1;
					break;
				}
			}

	/*		if (score >= beta) {
				// fail-soft beta-cutoff
				fail = 1;
				killer_move[ply-1] = m;
				best_move = m;
				best_score = score;
				break;
			}

			if (score > best_score) {
				best_score = score;
				if (score > alpha) {
					fail = 0;
					alpha = score;
					best_move = m;
				}
			}
	*/
#if NEGASCOUT
			//negascout
			beta2 = alpha+1;
#endif
		}

		if (!moved) {
			int d;
			// cannot go any further..
			// checkmate or stalemate...
			
			(*evals)++;
			
			d = 50 * (trait_search_depth - search_depth);
			if (color == engine_color) {
				// engine is in checkmate or stalemate
				if (get_attacks_to(b, last_one_64(b->color[color].king), !color))
					return MAX(alpha, (-500000 + d) * sm);
				else
					return MAX(alpha, (-400000 + d) * sm);
			} else {
				// opponent is in checkmate or stalemate
				if (get_attacks_to(b, last_one_64(b->color[color].king), !color))
					return MAX(alpha, (500000 - d) * sm);
				else
					return MAX(alpha, (400000 - d) * sm);
			}
		}

#if TRANSPOSITION_TABLE
	//	if (ply <= te->depth) {
			te->fail = fail;
			te->key = key;
			te->depth = search_depth;
			te->ply = ply;
			te->alpha = o_alpha;
			te->beta = o_beta;
			te->best_move = best_move;
			te->score = alpha;
	//	}
#endif
		return alpha;
	} else {
#if QUIESCENCE_SEARCH
		// get the standing pat score
		best_score = board_score(b) * sm;
		(*evals)++;
		if (beta <= best_score) {
#if TRANSPOSITION_TABLE
		//	te->fail = 0;
		//	te->key = key;
		//	te->depth = ply;
		//	te->score = best_score;
#endif
			return best_score;
		}

		alpha = MAX(alpha, best_score);

		fail = -1;

		move_count = get_capture_list(b, move_list, color);

#if NEGASCOUT
		beta2 = beta;
#endif
		for (i=0; i<move_count; i++) {
			m = *move_list++;

			b2 = *b;
			if (move_piece(b, m, color)) {
				// move leaves king in check
				continue;
			}
			moved = 1;
#if NEGASCOUT			
			score = -board_score_deep(b, m, !color, 0, 1, -beta2, -alpha, ply+1, evals);
			
			//negascout
			if (alpha < score && score < beta && i != 0) {
#endif				
				score = -board_score_deep(b, m, !color, 0, 1, -beta, -alpha, ply+1, evals);
#if NEGASCOUT
			}
#endif
			// undo move
			*b = b2;

			if (score > alpha) {
				fail = 0;
				alpha = score;

				if (alpha >= beta)
					break;
			}
		/*

			if (score >= beta) {
				// fail-soft beta-cutoff
				fail = 1;
				if (ply <= 32)
					killer_move[ply-1] = m;
				best_score = score;
				break;
			}

			if (score > best_score) {
				best_score = score;
				if (score > alpha) {
					fail = 0;
					alpha = score;
				}
			}
		*/
#if NEGASCOUT
			//negascout
			beta2 = alpha+1;
#endif
		}

		move_count = get_move_list(b, move_list, color);

		if (!moved && no_legal_moves(b, move_list, move_count, color)) {
			int d;
			// cannot go any further..
			// checkmate or stalemate...
			
			(*evals)++;
			
			d = 50 * (trait_search_depth - search_depth);
			if (color == engine_color) {
				// engine is in checkmate or stalemate
				if (get_attacks_to(b, last_one_64(b->color[color].king), !color))
					return MAX(alpha, (-500000 + d) * sm);
				else
					return MAX(alpha, (-400000 + d) * sm);
			} else {
				// opponent is in checkmate or stalemate
				if (get_attacks_to(b, last_one_64(b->color[color].king), !color))
					return MAX(alpha, (500000 - d) * sm);
				else
					return MAX(alpha, (400000 - d) * sm);
			}
			
			//return -500; // avoid or go after.. this works either way
		}

#if TRANSPOSITION_TABLE
	//	if (ply <= te->depth) {
		//	te->fail = fail;
		//	te->key = key;
		//	te->depth = ply;
		//	te->score = best_score;
	//	}
#endif
		return alpha;
#else
		(*evals)++;

		score = board_score(b) * sm;
#if TRANSPOSITION_TABLE
	//	if (te->key != key) {
			te->key = key;
			te->depth = search_depth;
			te->ply = ply;
			te->fail = 0;
			te->score = score;
	//	}
#endif
		return score;
#endif
	}
}

move_t find_best_move_search(board_t *b, move_t *move_list, int move_count, int search_depth)
{
	board_t b2;
	move_t best_move, m;
	int i, best_score, score, beta, evals = 0, last_eval = 0;
	char curmove_s[6];

#if MOVE_ORDER
	move_list = order_move_list(b, move_list);
#endif

	best_score = -INT_MAX;
#if NEGASCOUT
	beta = INT_MAX;
#endif
	for (i=0; i<move_count; i++) {
		m = *move_list++;

		b2 = *b;
		if (move_piece(b, m, current_color)) {
			// move leaves king in check
			continue;
		}
#if NEGASCOUT
		score = -board_score_deep(b, m, !current_color, search_depth-1, 0, -beta, -best_score, 1, &evals);

		// negascout
		if (best_score < score && score < INT_MAX) {
#endif
			score = -board_score_deep(b, m, !current_color, search_depth-1, 0, -INT_MAX, -best_score, 1, &evals);
#if NEGASCOUT
		}
#endif

		// undo move
		*b = b2;

		move_t2mstr(curmove_s, m);
		fprintf(of, "%s: %d .. %d evals\n", curmove_s, score, evals - last_eval);
		last_eval = evals;
		fflush(of);
		if (score > best_score) {
			best_score = score;
			best_move = m;
		}
#if NEGASCOUT
		// negascout
		beta = best_score+1;
#endif
	}
	fprintf(of, "Total evals: %d\n", evals);
	fflush(of);

	return best_move;
}

move_t find_best_move(board_t *b, move_t *move_list, int move_count, int search_depth)
{
	int i = search_depth;
	move_t m;

//	for (i=1; i<=search_depth; i++) {
		m = find_best_move_search(b, move_list, move_count, i);
//	}

	return m;
}







